package hebClustering.clusteringAlgorithms;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import hebClustering.Cluster;
import hebClustering.ClusterSet;
import hebClustering.vectorSpace.IVector;
import hebClustering.vectorSpace.distances.IDistance;

/**
 *	Implementation of the clustering algorithm K-means++ clustering.
 * 
 *	The algorithm operates exactly like the K-means algorithm, except the initialization phase.
 *	
 * 	@see <a href="http://en.wikipedia.org/wiki/K-means%2B%2B" target="_blank">K-means++ clustering</a>
 */
public class KMeansPPClustering extends KMeansClustering{

	public KMeansPPClustering(int K, int I, IDistance distance) {
		super(K, I, distance);
	}
	
	protected void initializeMeans(Collection<IVector> dataSet,ClusterSet clusterSet) {

		List<IVector> resultSet = new LinkedList<IVector>();
		List<IVector> vectorList = new LinkedList<IVector>(dataSet);
		
		Random random = new Random();
		IVector firstVector = vectorList.remove(random.nextInt(vectorList.size()));
		resultSet.add(firstVector);
		
		double distances[] = new double[vectorList.size()];
		
		while (resultSet.size() < K){
			double sum = 0;
			for (int i = 0; i < vectorList.size(); i++){
				IVector v = vectorList.get(i);
				IVector nearestMean = getNearestMean(resultSet,v);
				double d = Math.pow(distance.calc(v, nearestMean),2);
				sum += d;
				distances[i] = sum;
			}
			
			double r = random.nextDouble() * sum;
			for (int i = 0; i < distances.length; i++){
				if (distances[i] >= r){
					IVector nextVector = vectorList.remove(i);
					resultSet.add(nextVector);
					break;
				}
			}
		}
		
		for (int i = 0; i< K; i++){
			Cluster c = new Cluster(resultSet.get(i));
			clusterSet.add(c);
		}
		
	}

	private IVector getNearestMean(List<IVector> resultSet, IVector v) {
		IVector nearest = null;
		double minDist = Double.MAX_VALUE;
		
		for (IVector vector : resultSet){
			double dist = distance.calc(v, vector);
			if (dist < minDist){
				minDist = dist;
				nearest = vector;
			}
		}
		
		return nearest;
	}

}
